const BinaryNode = require('./树节点/binarynode')
const Queue = require('../队列/queue')
const Stack = require('../stack')

//二叉树
class BinaryTree {
    constructor(root = null) {
        this.root = root
        this._i = 0
    }
    // 静态方法：标明空子树的前序遍历数组构造二叉树
    static createByPreArr(arr) {
        //调用内部递归构建
        let tr = new BinaryTree()
        tr.root = tr._create(arr)
        return tr
    }
    // 静态全局变量_i,外部不可访问
    static _i = 0
    _create(arr) {
        let p = null
        let element = arr[BinaryTree._i]
        BinaryTree._i++
        if (element !== null) {
            p = new BinaryNode(element)
            p.left = this._create(arr)
            p.right = this._create(arr)
        }
        return p
    }
    // 根节点数据域
    getRootData() {
        return this.root.data
    }
    // 判空
    isEmpty() {
        return this.root === null
    }
    // 树高
    height() {
        return this._height(this.root)
    }
    _height(subroot) {
        if (subroot === null) {
            return 0
        } else {
            // console.log(subroot.left.toString());
            let left_tree = this._height(subroot.left)
            let right_tree = this._height(subroot.right)
            return (left_tree >= right_tree) ? left_tree + 1 : right_tree + 1
        }
    }
    // 节点总数
    numberOfNode() {
        return this._numberOfNode(this.root)
    }
    _numberOfNode(subroot) {
        if (subroot === null) {
            return 0
        } else {
            return 1 + this._numberOfNode(subroot.left) + this._numberOfNode(subroot.right)
        }
    }
    // 清空
    clear() {
        this.root = null
    }

    //返回先序遍历的描述输出
    toString() {
        this._toString(this.root)
        process.stdout.write('\n')
    }
    _toString(subroot) {
        if (subroot !== null) {
            process.stdout.write(subroot.toString() + " ")
            this._toString(subroot.left)
            this._toString(subroot.right)
        } else {
            process.stdout.write('^ ')
        }
    }
    /********************************四种遍历**************************** */
    // 前序遍历输出
    preOrder() {
        process.stdout.write('前序遍历：')
        this._preOrder(this.root)
        process.stdout.write('\n')
    }
    _preOrder(subroot) {
        if (subroot !== null) {
            process.stdout.write(subroot.toString() + " ")
            this._preOrder(subroot.left)
            this._preOrder(subroot.right)
        }
    }
    //非递归前序遍历输出
    preOrderByNoRecursion() {
        let stack = new Stack()
        let p = this.root
        while (!stack.isEmpty() || p !== null) {
            if (p !== null) {
                process.stdout.write(p.toString() + ' ')
                stack.push(p)
                p = p.left
            } else {
                p = stack.pop()
                p = p.right
            }
        }
        process.stdout.write('\n')
    }
    // 中序遍历输出
    inOrder() {
        process.stdout.write('中序遍历：')
        this._inOrder(this.root)
        process.stdout.write('\n')
    }
    _inOrder(subroot) {
        if (subroot !== null) {
            this._inOrder(subroot.left)
            process.stdout.write(subroot.toString() + " ")
            this._inOrder(subroot.right)
        }
    }
    // 非递归中序遍历输出
    inOrderByNoRecursion() {
        let stack = new Stack()
        let p = this.root
        while (!stack.isEmpty() || p !== null) {
            if (p !== null) {
                stack.push(p)
                p = p.left
            } else {
                p = stack.pop()
                process.stdout.write(p.toString() + " ")
                p = p.right
            }
        }
        process.stdout.write('\n')
    }
    // 后序遍历输出
    postOrder() {
        process.stdout.write('后序遍历：')
        this._postOrder(this.root)
        process.stdout.write('\n')
    }
    _postOrder(subroot) {
        if (subroot !== null) {
            this._postOrder(subroot.left)
            this._postOrder(subroot.right)
            process.stdout.write(subroot.toString() + " ")
        }
    }
    // 非递归后序遍历输出（传统栈）
    postOrderByNoRecursion() {
        let stack = new Stack()
        let p = this.root
        let temp
        while (!stack.isEmpty() || p !== null) {
            if (p !== null) {
                stack.push(p)
                p = p.left
            } else {
                // 读栈顶而非直接pop
                // 若直接pop，可能进入右子节点访问后找不到回溯的路径
                p = stack.peek()
                // p有右孩子，且没有被访问过
                if (p.right !== null && p.right !== temp) {
                    p = p.right
                } else {
                    p = stack.pop()
                    process.stdout.write(p.toString() + " ")
                    temp = p
                    p = null
                }
            }
        }
        process.stdout.write('\n')
    }
    // 非递归后序遍历（双栈）
    postOrderByDoubleStack() {
        let p = this.root
        let input_stack = new Stack()
        input_stack.push(p)
        let output_stack = new Stack()
        while(!input_stack.isEmpty()) {
            p = input_stack.peek()
            output_stack.push(input_stack.pop())
            if(p.left !== null) {
                input_stack.push(p.left)
            }
            if(p.right !== null) {
                input_stack.push(p.right)
            }
        }
        while(!output_stack.isEmpty()) {
            process.stdout.write(output_stack.pop()+" ")
        }
        process.stdout.write('\n')
    }
    //层序遍历输出
    levelOrder() {
        process.stdout.write("层序遍历：")
        let queue = new Queue()
        queue.enQueue(this.root)
        let p
        while (!queue.isEmpty()) {
            p = queue.deQueue()
            process.stdout.write(p.toString() + " ")
            if (p.left !== null) {
                queue.enQueue(p.left)
            }
            if (p.right !== null) {
                queue.enQueue(p.right)
            }
        }
        process.stdout.write('\n')
    }
}


module.exports = BinaryTree
//测试用例
// let arr = ['A', 'B', 'D', null, 'E', null, null, null, 'C', 'F', null, null, 'G', null, null]
// let tr = BinaryTree.createByPreArr(arr)
// tr.toString()
// tr.preOrder()
// tr.preOrderByNoRecursion()
// tr.inOrder()
// tr.inOrderByNoRecursion()
// tr.postOrder()
// tr.postOrderByNoRecursion()
// tr.levelOrder()
// tr.postOrderByDoubleStack()